//题目:
// 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
// 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
#include<iostream>
#include<queue>
#include<vector>

using namespace std;
//代码:
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        queue<Node*> q;//存放每层结点
        q.push(root);
        vector<vector<int>> ret; 
        int level_count=q.size();      //记录同层结点个数
        while(!q.empty() && q.front()!=nullptr)
        {
            //1.将parent所在层的所有结点出队列，及其子节点入队列
            vector<int> v;
            while(level_count>0 && q.front()!=nullptr)
            {
                Node* parent=q.front();
                for(int i=0;i<parent->children.size();i++)
                    q.push(parent->children[i]);//子节点入队列
                q.pop();//同层结点出队列
                v.push_back(parent->val);//记录同层结点的值
                level_count--;
            }
            //2.将v放入ret中
            ret.push_back(v);
            //3.更新level_count的值
            level_count=q.size();
        } 
        return ret;
    }
};